#include <iostream>
#include <vector>
#include <string>
using namespace std;

//输出1到n中每个整数二进制表示中1的个数

vector<int> countBits(int n)
{
    vector<int> res(n + 1);
    for (int i = 0; i <= n; i++)
    {
        res[i] = res[i >> 1] + (i % 2);
    }
    return res;
}